package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class ValidateBinarySearchTree {
	
	//方法一：我写的，中序遍历模式递归版
    public boolean isValidBST(TreeNode root) {
    	Integer[] prev = {null};
    	boolean[] result = {true};
    	isValidBST(root, prev, result);
    	return result[0];
    }
    
    private void isValidBST(TreeNode node, Integer[] prev, boolean[] result) {
    	if(node == null || !result[0]) return;
    	isValidBST(node.left, prev, result);
    	if(prev[0] != null && prev[0] >= node.val) {
    		result[0] = false;
    		return;
    	}
    	prev[0] = node.val;
    	isValidBST(node.right, prev, result);
    }
    
    //方法二：我写的，中序遍历模式迭代版
    public boolean isValidBST2(TreeNode root) {
    	LinkedList<TreeNode> stack = new LinkedList<>();
    	TreeNode p = root;
    	Integer prev = null;
    	while(!stack.isEmpty() || p != null) {
    		if(p != null) {
    			stack.push(p);
    			p = p.left;
    		}else {
    			TreeNode node = stack.pop();
    			if(prev != null && prev >= node.val)
    				return false;
    			prev = node.val;
    			p = node.right;
    		}
    	}
    	return true;
    }
    
    //方法三：别人写的，前序遍历模式递归版
    public boolean isValidBST3(TreeNode root) {
        return isValidBST3(root, null, null);
    }

    private boolean isValidBST3(TreeNode root, Integer min, Integer max) {
        if(root == null) return true;
        if(min != null && root.val <= min) return false;
        if(max != null && root.val >= max) return false;
        
        return isValidBST3(root.left, min, root.val) && isValidBST3(root.right, root.val, max);
    }
    
}
